package xfg.array_list;

import java.util.Arrays;

/**
 * @author 小傅哥，微信：fustack
 * @description
 * @github https://github.com/fuzhengwei
 * @Copyright 公众号：bugstack虫洞栈 | 博客：https://bugstack.cn - 沉淀、分享、成长，让自己和他人都能有所收获！
 *
 *     数据结构中有哪些是线性表数据结构？
 *     数组，栈，队列
 *     数组的元素删除和获取，时间复杂度是多少？
 *     获取O(1) 可以根据索引精准的获取到内存地址
 *     删除 最坏的结果就是O(N)
 *     ArrayList 中默认的初始化长度是多少？
 *     10
 *     ArrayList 中扩容的范围是多大一次？
 *     ArrayList 是如何完成扩容的，System.arraycopy 各个入参的作用是什么？
 *
 * #
 */
public class ArrayList<E> implements List<E> {

	/**
	 * 默认初始化空间
	 */
	private static final int DEFAULT_CAPACITY = 10;

	/**
	 * 空元素
	 */
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	/**
	 * ArrayList 元素数组缓存区
	 */
	transient Object[] elementData;

	/**
	 * List 集合元素数量
	 */
	private int size;

	public ArrayList() {
		// 默认给个空的元素，当开始添加元素的时候在初始化长度
		this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	}

	/**
	 * 1. 判断当前容量与初始化容量，使用 Math.max 函数取最大值最为最小初始化空间。
	 * 2. 接下来是判断 minCapacity 和元素的数量，是否达到了扩容。
	 * 首次创建 ArrayList 是一定会扩容的，也就是初始化 DEFAULT_CAPACITY = 10 的容量。
	 * 3. Arrays.copyOf 实际上是创建一个新的空间数组，之后调用的 System.arraycopy 迁移到新创建的数组上。
	 * 这样后续所有的扩容操作，也就都保持统一了。
	 * 4. ArrayList 扩容完成后，就是使用 elementData[size++] = e; 添加元素操作了。
	 *
	 * @param e
	 * @return
	 *
	 * 这是一份简化后的 ArrayList#add 操作
	 *
	 * 1. 判断当前容量与初始化容量，使用 Math.max 函数取最大值最为最小初始化空间。
	 * 2. 接下来是判断 minCapacity 和元素的数量，是否达到了扩容。首次创建 ArrayList 是一定会扩容的，也就是初始化 DEFAULT_CAPACITY = 10 的容量。
	 * 3. Arrays.copyOf 实际上是创建一个新的空间数组，之后调用的 System.arraycopy 迁移到新创建的数组上。这样后续所有的扩容操作，也就都保持统一了。
	 * 4. ArrayList 扩容完成后，就是使用 elementData[size++] = e; 添加元素操作了。
	 */
	@Override
	public boolean add(E e) {
		// 确保内部容量
		int minCapacity = size + 1;
		if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
			minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
		}
		// 判断扩容操作
		if (minCapacity - elementData.length > 0) {
			int oldCapacity = elementData.length;
			int newCapacity = oldCapacity + (oldCapacity >> 1);
			if (newCapacity - minCapacity < 0) {
				newCapacity = minCapacity;
			}
			elementData = Arrays.copyOf(elementData, newCapacity);
		}
		// 添加元素
		elementData[size++] = e;
		return true;
	}

	@Override
	public E remove(int index) {
		// 0 1 2 3 4
		E oldValue = (E) elementData[index];
		// 计算 索引后面的 数据亮
		int numMoved = size - index - 1;
		if (numMoved > 0) {
			// 从原始数组的某个位置，拷贝到目标对象的某个位置开始后n个元素
			System.arraycopy(elementData, index + 1, elementData, index, numMoved);
		}
		elementData[--size] = null; // clear to let GC do its work
		return oldValue;
	}

	@Override
	public E get(int index) {
		return (E) elementData[index];
	}

	@Override
	public String toString() {
		return "ArrayList{" +
				"elementData=" + Arrays.toString(elementData) +
				", size=" + size +
				'}';
	}

}
